#include <vector>
#include <unordered_set>
#include <iostream>

using namespace std;

class Solution {
private:
    int k ;
    int n;
    vector<vector<int>> ans;
    void forward(int deep, vector<int> his, int sum, int last_select) {
        if (deep > k) {
            return;
        }
        if (sum == n) {
            if (deep != k) {
                return;
            }
            ans.push_back(his);
            return;
        }
        for (int i = last_select + 1; i < 10; i++) {
            sum += i;
            his.push_back(i);
            forward(deep + 1, his, sum, i);
            his.pop_back();
            sum -= i;
        }
    }
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        this->k = k;
        this->n = n;
        forward(0, {}, 0, 0);
        return ans;
    }
};

int main() {
    Solution solution;
    vector<vector<int>> output = solution.combinationSum3(3, 9);
    return 0;
}